package Test;

/**
 * @author Kevin
 * @date 2020/3/2 20:09
 */
public class HeapSortAgain {

    public int findKthNum(int[] arr, int k) {
        //首先对1到k-1的元素建堆
        buildHeap(arr, k);
        //然后对k-arr.length的元素继续堆化
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < arr[0]) continue;
            swap(arr, i, 0);
            heapify(arr, k, 0);
        }
        //返回最终的arr[0]，小顶堆堆顶
        return arr[0];
    }

    public void buildHeap(int[] arr, int k) {
        for(int i = (k-1)/2; i >= 0; i--) {
            heapify(arr, k, i);
        }
    }

    public void heapify(int[] arr, int k, int i) {
        int minPos = i;
        while (true) {
            if (i * 2 + 1 < k && arr[2 * i + 1] < arr[i]) minPos = 2 * i + 1;
            if (i * 2 + 2 < k && arr[2 * i + 2] < arr[minPos]) minPos = 2 * 2 + 2;
            if (minPos == i) break;//i是最小
            swap(arr, i, minPos);
            i = minPos;//向下寻找有没有更小的
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
